#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define NORMAL 0
#define THRENA 1 
// 后序 
 
typedef struct Node {
    int val, ltag, rtag;
    struct Node *lchild, *rchild;
} Node;
 
Node *getNewNode(int val) {
    Node *root = (Node *)malloc(sizeof(Node));
    root->lchild = root->rchild = NULL;
    root->rtag = root->ltag = NORMAL;
    root->val = val;
    return root;
}
 
Node *insert(Node *root, int val) {
    if (!root) return getNewNode(val);
    if (root->val == val) return root;
    if (root->val > val) root->lchild = insert(root->lchild, val);
    else root->rchild = insert(root->rchild, val);
    return root;
}
 
void build_Thread(Node *root) {
    if (!root) return ; 
    static Node *pre = NULL;
    build_Thread(root->lchild);
    build_Thread(root->rchild);
    if (root->ltag == NORMAL) {
        root->lchild = pre;
        root->ltag = THRENA;
    }
    if (pre && root->rtag == NORMAL) {
        pre->rchild = root;
        pre->rtag = THRENA;
    }
    pre = root;
    return ;
}
 
Node *most_left(Node *root) {
    while (root && root->ltag == THRENA && root->lchild) root = root->lchild;
    return root;
}
 
void output(Node *root) {
    if (!root) return ;
    Node *p = most_left(root);
    while (p) {
        printf("%d ", p->val);
        if (p->rtag == THRENA) p = p->rchild;  
        else if (p->rtag == NORMAL) break;
    }
    return ;
}
 
 
void back_order(Node *root) {
    if (!root) return ;
    if (root->ltag == NORMAL) back_order(root->lchild);
    if (root->rtag == NORMAL) back_order(root->rchild);
    printf("%d ", root->val);
    return ;
}
 
void preface(Node *root) {
    if (!root) return ;
    printf("%d(", root->val);
    if (root->ltag == NORMAL) preface(root->lchild);
    printf(",");
    if (root->rtag == NORMAL) preface(root->rchild);
    printf(")");
    return ;
}
 
void clearNode(Node *root) {
    if (!root) return ;
    if (root->ltag == NORMAL) clearNode(root->lchild);
    if (root->rtag == NORMAL) clearNode(root->rchild);
    free(root);
    return ;
}
 
 
int main() {
    srand(time(0)); 
    Node *root = NULL;
    for (int i = 0; i < 10; i++) {
        int val = rand() % 100;
        root = insert(root, val);
    }
    preface(root);
    putchar(10);
    back_order(root);
    putchar(10);
    build_Thread(root);
    output(root);
    putchar(10);
    clearNode(root);
    return 0;
}
